package leetcode_500;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *ArithmeticSlicesIISubsequence_446 判断一个int数组里有多少算术子切片
 *describe:用动态规划 注意Int越界 AC 18%
 *2018年8月21日 下午5:31:43
 */
public class ArithmeticSlicesIISubsequence_446 {
	
	public static void main(String[] args) {
		ArithmeticSlicesIISubsequence_446 test=new ArithmeticSlicesIISubsequence_446();
		//test.numberOfArithmeticSlices(new int[] {2,4,6,8,10});
		test.numberOfArithmeticSlices(new int[] {0,2000000000,-294967296});
	}
	
	/**
	 * describe:动态规划 二维数组 dp[index][diff]
	 * 2018年8月21日 下午4:43:40
	 * @param A
	 * @return
	 * int
	 */
	public int numberOfArithmeticSlices(int[] A) {
        /*int dp[][]=new int[A.length][Integer.MAX_VALUE];
        int res=0;
        for(int i=1;i<A.length;++i) {
        	for(int j=i-1;j>=0;--j) {
        		int diff=A[i]-A[j];
        		dp[i][diff]=dp[j][diff]+1;
        		if(dp[i][diff]>1)
        			++res;
        	}
        }
        return res;*/
		if(A.length<3)
			return 0;
		Map<Integer,Map<Long,Integer>> dp=new HashMap<Integer,Map<Long,Integer>>();
		int res=0;
		dp.put(0, new HashMap<Long,Integer>());
		for(int i=1;i<A.length;++i) {
			Map<Long,Integer> nowI=new HashMap<Long,Integer>();
			dp.put(i, nowI);
			for(int j=i-1;j>=0;--j) {
				long diff=(long)A[i]-(long)A[j];//越界情况必须考虑
				Map<Long,Integer> nowJ=dp.get(j);
                int pre=nowI.containsKey(diff)?nowI.get(diff):0;
				if(nowJ.containsKey(diff)) {
					int now=nowJ.get(diff);
					if(now>0)
						res+=now;
					nowI.put(diff, now+1+pre);
				}
				else {
					nowI.put(diff, 1+pre);
				}
			}
		}
		return res;
    }
}
